home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / gamesrc / mancala / ab.c < prev    next >
C/C++ Source or Header  |  1994-08-24  |  2KB  |  87 lines
  1. /* ab.c
  2.  *
  3.  * Crude, simple alpha-beta search.
  4.  *
  5.  * No pruning, yet.
  6.  *
  7.  * Requires the following to be defined:
  8.  *   ab_position_t:  Type that defines a board position.
  9.  *   ab_score_t:  Score type for score of a move.
  10.  *   AB_WIN_SCORE:  Score that signifies a win.
  11.  *   AB_MAX_MOVES:  Max moves that will ever be available from a single
  12.  *     position.
  13.  *   ab_move_t:  Type that definies a move.
  14.  *   ab_storage_t:  Data needed to store a move's effects and undo them.
  15.  *   ab_score_t AB_MOVE_VAL(move):  Value of a move.
  16.  *   int  AB_PLAYER_TO_MOVE(pos):  0 or 1.
  17.  *   int  ab_generate_moves(pos, moves);
  18.  *   ab_score_t ab_do_move(position, move, storage):  Make move to position.
  19.  *   void ab_undo_move(position, storage):  Undo a move.
  20.  *   int  ab_move_cmp(mv1, mv2):  Return >0 if mv1 has a higher score,
  21.  *     is better, <0 if mv2 is better.  Should never return 0.
  22.  */
  23.  
  24.  
  25. #include "mancala.h"
  26. #include <stdio.h>
  27.  
  28.  
  29. static ab_score_t  rsearch(ab_position_t *pos, int depth,
  30.                                                      ab_move_t *bestmove);
  31.  
  32.  
  33. ab_move_t  ab_search(ab_position_t *pos, int depth)  {
  34.     ab_move_t  result;
  35.     ab_score_t  score;
  36.  
  37.     do  {
  38.         score = rsearch(pos, depth, &result);
  39.         --depth;
  40.     } while ((score <= -AB_WIN_SCORE) && (depth > 0));
  41.     return(result);
  42. }
  43.  
  44.  
  45. static ab_score_t  rsearch(ab_position_t *pos, int depth,
  46.                                                      ab_move_t *bestmove)  {
  47.     ab_move_t  moves[AB_MAX_MOVES];
  48.     int  n_moves, i, tomove = AB_PLAYER_TO_MOVE(*pos);
  49.     ab_storage_t  mvmade;
  50.     ab_score_t  bscore, cscore, mscore;
  51.  
  52.     bscore = -AB_WIN_SCORE;
  53.     n_moves = ab_generate_moves(pos, moves);
  54.     if (n_moves == 0)
  55.         return(0);
  56.     qsort(moves, n_moves, sizeof(ab_move_t), ab_move_cmp);
  57.     if (bestmove != NULL)
  58.         *bestmove = moves[0];
  59.     if (AB_MOVE_VAL(moves[0]) >= AB_WIN_SCORE)
  60.         return(AB_WIN_SCORE);
  61.     else if (AB_MOVE_VAL(moves[0]) <= -AB_WIN_SCORE)
  62.         return(-AB_WIN_SCORE);
  63.     if (depth == 1)
  64.         return(AB_MOVE_VAL(moves[0]));
  65.     for (i = 0;  i < n_moves;  ++i)  {
  66.         cscore = ab_do_move(pos, &moves[i], &mvmade);
  67.         mscore = rsearch(pos, depth - 1, NULL);
  68.         if (AB_PLAYER_TO_MOVE(*pos) != tomove)
  69.             mscore = -mscore;
  70.         ab_undo_move(pos, &mvmade);
  71.         if (mscore >= AB_WIN_SCORE)  {
  72.             if (bestmove != NULL)
  73.                 *bestmove = moves[i];
  74.             return(AB_WIN_SCORE);
  75.         }
  76.         if (mscore > -AB_WIN_SCORE)  {
  77.             cscore += mscore;
  78.             if (cscore > bscore)  {
  79.                 bscore = cscore;
  80.                 if (bestmove != NULL)
  81.                     *bestmove = moves[i];
  82.             }
  83.         }
  84.     }
  85.     return(bscore);
  86. }
  87.